/*
 * from : http://blog.csdn.net/livelylittlefish/archive/2008/08/05/2768348.aspx
 * can also see in : http://zhedahht.blog.163.com/blog/static/25411174200732494452636/
 */
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <assert.h>

int digit_number_s( int input, int digit  = 1 )
{
	int number = 0;
	for( int i = 0; i <= input; ++i ) {
		for( int j = i; j > 0; j = j/10 ) {
			if( j % 10 == digit )
				number ++;
		}
	}

	return number;
}

int pow10( int n )
{
	int r = 1;
	for( int i = 0; i < n; i++ )
		r *= 10;
	return r;
};

int max_digit_number( int n )
{
	if( 0 == n )
		return 0;
	return 10 * max_digit_number( n - 1 ) + pow10( n - 1 );
}

int digit_number( int input, int digit  = 1 )
{

	if( 0 == input )
		return 0;
	int k = 1;
	for( ; pow10( k ) <= input; k++ )
		;
	k--;
	if( 0 == k ) {
		return input >= digit;
	}

	int number = 0;
	// number += max_digit_number( k );
	number += input / pow10( k ) * max_digit_number( k );
	if( input / pow10( k ) == digit ) {
		number += input % pow10( k ) + 1;
	}
	else if( input / pow10( k ) > digit ) {
		number += pow10( k );
	}
	number += digit_number( input % pow10( k ), digit );
	return number;
}

int main( int argc, char *argv[] )
{
	int input = atoi( argv[1] );
	int digit = atoi( argv[2] );
	printf( "%d\n", digit_number( input, digit ) );
	printf( "%d\n", digit_number_s( input, digit ) );
	for( int i = 0; i <= input; i++ ) {
		assert( digit_number( i, digit ) == digit_number_s( i, digit ) );
	}
}

